package leetcode.datastructure.array;

import java.util.Arrays;

public class Program169MajorityElement {
    public Program169MajorityElement() {
    }

    public int majorityElement(int[] nums) {
//        return time(nums);
        return space(nums);
    }

    /**
     * Boyer-Moore投票算法，众数
     * 空间复杂度O(1)
     * 时间复杂度O(N)
     * @param nums
     * @return
     */
    public int space(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    /**
     * 时间复杂度O(logN)
     * 空间复杂度O(N)
     * @param nums
     * @return
     */
    public int time(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        if (length == 2) {
            return nums[0] == nums[1] ?nums[0] : -1;
        }
        Arrays.sort(nums);
        int left = 0, right = length - 1;
        int mid = makeMid(left, right);
        if (nums[left] == nums[mid] || nums[right] == nums[mid]) {
            return nums[mid];
        }
        int leftMid = makeMid(left, mid);
        int rightMid = makeMid(mid, right);
        if (nums[leftMid] == nums[mid] || nums[rightMid] == nums[mid]) {
            return nums[mid];
        } else {
            return -1;
        }
    }

    public int makeMid(int left, int right) {
        return (right - left) / 2 + left;
    }

    public static void main(String[] args) {
        Program169MajorityElement myStack = new Program169MajorityElement();
//        int[] nums = {3,2,3};
//        System.out.println(myStack.majorityElement(nums)); // 返回
//        int[] nums1 = {2,2,1,1,1,2,2};
//        System.out.println(myStack.majorityElement(nums1)); // 返回
//        int[] nums2 = {2,3};
//        System.out.println(myStack.majorityElement(nums2)); // 返回
        int[] nums3 = {12,52,12,70,12,61,12,12,50,72,82,12,11,25,28,43,40,12,12,53,12,12,98,12,12,92,81,2,12,15,40,12,12,9,12,31,12,12,12,12,77,12,12,50,12,12,12,93,41,92,12,12,12,12,12,12,12,12,12,37,48,14,12,70,82,12,80,12,12,12,12,56,30,12,8,12,50,12,20,12,21,97,12,42,12,10,12,38,73,15,9,11,79,12,12,28,51,12,15,12};
        System.out.println(myStack.majorityElement(nums3)); // 返回
    }
}
